package tree;
import java.util.*;

/* 
    根据前序和中序确定二叉树
*/
public class Ex105 {
    class Solution {
        int[] inorder;
        int[] preorder;
        Map<Integer, Integer> map = new HashMap<>();
        public TreeNode buildTree(int[] preorder, int[] inorder) {
            if (preorder.length != inorder.length) return null;
            for (int i = 0; i < inorder.length; i++) {
                map.put(inorder[i], i);
            }
            return dfs(0, 0, inorder.length - 1);
        }
    
        public TreeNode dfs(int left, int idx, int right) {
            if (left > right) return null;
            TreeNode root = new TreeNode(preorder[idx]);
            int r = map.get(preorder[idx]); //根节点在中序的位置
            //左子树长度
            int len_left = r - left;
            root.left = dfs(left, idx + 1, r - 1);
            root.right = dfs(r + 1, idx + len_left + 1, right);
            return root;
        }
    }
    
}
